package com.mj.Tree;

import javafx.scene.Parent;

import java.util.Comparator;

/**
 * @Author: LDeng
 * @Date: 2021-03-03 13:25
 */
public class AVLTree<E> extends BalanceBinarySearchTree<E> {

    public AVLTree() {
        this(null);
    }

    public AVLTree(Comparator<E> comparator) {
        super(comparator);
    }

    @Override
    protected void afterAdd(Node<E> node) {
        //修复失衡节点， 再向上的会自动修复
        while ((node = node.parent) != null) {//
            //判断是否平衡
            if (isBalanced(node)) {//平衡==>更新高度
               updateHeight(node);
            } else {//不平衡==>恢复平衡
                rebalance2(node);//能来到这里， node就是图片上的g节点，
                break;//整棵树恢复平衡, 直接break， 不需要再向上找父节点.
            }
        }
    }

    //AVL树中具体实现afterRemove
    @Override
    protected void afterRemove(Node<E> node,Node<E> replacement) {
        //修复失衡节点， 再向上的会自动修复
        while ((node = node.parent) != null) {//
            //判断是否平衡
            if (isBalanced(node)) {//平衡==>更新高度
                updateHeight(node);
            } else {//不平衡==>恢复平衡
                rebalance2(node);//能来到这里， node就是图片上的g节点，
            }
        }
    }

    private boolean isBalanced(Node<E> node){

        return Math.abs(((AVLNode<E>)node).balanceFactor())<=1;
    }

    @Override
    protected Node<E> createNode(E element, Node<E> parent) {
        return new AVLNode<>(element, parent);
    }


    //利用最终排列是abcdefg d为中心
    public void rebalance(Node<E> grand){
        Node<E> parent=((AVLNode<E>)grand).tallerChild();
        Node<E> node=((AVLNode<E>)parent).tallerChild();
        if(parent.isLeftChind()){//左边
            if(node.isLeftChind()){//LL
                //对照图写
                rotate(grand,node.left,node,node.right,parent,parent.right,grand,grand.right);
            }else{//LR
                rotate(grand, parent.left,parent,node.left,node,node.right,grand,grand.right);
            }
        }else{//右边
            if(node.isLeftChind()){//RL
                rotate(grand,grand.left,grand, node.left,node,node.right,parent,parent.right);
            }else{//RR
                rotate(grand,grand.left,grand,parent.left,parent,node,node.left,node.right);
            }
        }

    }

    //旋转恢复平衡
    public void rebalance2(Node<E> grand){
        Node<E> parent=((AVLNode<E>)grand).tallerChild();
        Node<E> node=((AVLNode<E>)parent).tallerChild();
        if(parent.isLeftChind()){//左边
            if(node.isLeftChind()){//LL
                rotateRight(grand);
            }else{//LR
                rotateLeft(parent);
                rotateRight(grand);
            }
        }else{//右边
            if(node.isLeftChind()){//RL
                rotateRight(parent);
                rotateLeft(grand);
            }else{//RR
                rotateLeft(grand);
            }
        }
    }

    @Override
    protected void afterRotate(Node<E> grand, Node<E> p, Node<E> child) {
        super.afterRotate(grand, p, child);
        //更新节点高度
        updateHeight(grand);
        updateHeight(p);
    }

    @Override
    protected void rotate(Node<E> r, Node<E> a, Node<E> b, Node<E> c, Node<E> d, Node<E> e, Node<E> f, Node<E> g) {
        super.rotate(r, a, b, c, d, e, f, g);
        updateHeight(b);
        updateHeight(f);
        updateHeight(d);
    }

    private void updateHeight(Node<E> node){
        AVLNode<E> avlNode=(AVLNode<E>)node;
        avlNode.updateHeight();
    }

    private static class AVLNode<E> extends Node<E> {
        int height=1;//节点创建出来默认高度为1

        public AVLNode(E element, Node<E> parent) {
            super(element, parent);
        }

        //获取节点的平衡因子（左右节点的高度差）
        public int balanceFactor() {
            int leftHeight = (left == null ? 0 : ((AVLNode<E>)left).height);//强转为AVL左节点
            int rightHeight = (right == null ? 0 : ((AVLNode<E>)right).height);
            return leftHeight - rightHeight;
        }

        public int updateHeight(){
            int leftHeight = (left == null ? 0 : ((AVLNode<E>)left).height);//强转为AVL左节点
            int rightHeight = (right == null ? 0 : ((AVLNode<E>)right).height);
            height=1+Math.max(leftHeight,rightHeight);
            return height;
        }

        public Node<E> tallerChild(){
            int leftHeight = (left == null ? 0 : ((AVLNode<E>)left).height);//强转为AVL左节点
            int rightHeight = (right == null ? 0 : ((AVLNode<E>)right).height);
            if(leftHeight>rightHeight) return left;
            if(leftHeight<rightHeight) return right;
            return isLeftChind()?left:right;
        }

        @Override
        public String toString() {
            String parentString = "null";
            if (parent != null) {
                parentString = parent.element.toString();
            }
            return element + "(↑" + parentString + "_h="+height+")";
        }
    }


}
